本场链接:Codeforces Round #586 (Div. 1 + Div. 2)

闲话

本场ABC都比较简单,D稍微有点麻烦.C这个傻逼题做复杂了,我原地退役.jpg.

A. Cards

题目大意:有很多张卡片上面写着zero或者one.现在把他们按字母分成了很多张小纸片,每个纸片上只有一个字母,问最大能拼出的序列是多少.

思路

显然一个zero必须要有一个z,一个one必须要有一个n.所以zero就有z的字母个数的数量,one就有n的字母个数的数量,直接统计输出,让one的先输出即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	string s;cin >> s;
	int a = 0,b = 0;
	for(int i = 0;i < n;++i)
		if(s[i] == 'n')	++a;
		else if(s[i] == 'r')	++b;
	while(a--)	cout << 1 << " ";
	while(b--)	cout << 0 << " ";
	cout << endl;	
    return 0;
}

B. Multiplication Table

题目大意:最开始有一组长度为$n$的序列.以及一个$n*n$的矩阵M,$M_{ij}$的值这样给定:$a_i*a_j$.现将M的主对角线上的所有元素擦除,要求输出一组原有的序列$a$的构造方案使整个矩形的条件满足.

思路

显然对于每个不是$1/2/3$的元素来说,可以这么干:$a_x = \sqrt{M_{1,x}*M_{2,x} / M_{1,2}}$得到他的值,而对于是$1/2/3$的数,具体讨论一下也可以得到相应的构造方法,再次就不赘述了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1007;
int a[N][N];
int main()
{
	int n;scanf("%d",&n);
	for(int i = 1;i <= n;++i)	
		for(int j = 1;j <= n;++j)
			scanf("%d",&a[i][j]);
	for(int i = 1;i <= n;++i)
	{
		if(i == 1)	printf("%d ",(int)sqrt(1ll * a[1][2] * a[1][3] / a[2][3]));
		else if(i == 2)	printf("%d ",(int)sqrt(1ll * a[1][2] * a[2][3] / a[1][3]));
		else if(i == 3)	printf("%d ",(int)sqrt(1ll * a[1][3] * a[2][3] / a[1][2]));
		else	printf("%d ",(int)sqrt(1ll * a[1][i] * a[2][i] / a[1][2]));
	}
    return 0;
}

C. Substring Game in the Lesson

题目大意:有两个毒瘤在玩博弈游戏.这个游戏是在一个字符串$s$的一个前缀子串上进行的.最开始的时候定义两个指针$l,r$都在串的最后一位,每次可以这样移动指针:找到一个新的区间[l',r']使新划分出来的字符串字典序比原来的更小,满足这个条件就可以让原来的两个指针移动到对应的位置上.无法操作的人输.问是否先手必胜,先手为Ann,后手为Mike.要求输出对于所有可能的前缀子串的结果.

数据范围:
$1 \leq |s| \leq 5 * 10^5$

思路

由于题目的样例实在是太垃圾了,随便搞个长点的做一下试试:bcbacbaccaba.显然第一步一定是后手赢的,先手根本没法移动手上就一个b.再然后是bc,由于有一个更小的b在前面,这导致先手可以一步取完所有的元素而获得胜利.bcb就不行了,因为b和前面最小的字典序的b是一样的,导致Mike走到了一个必胜局面,再往后的一个bcba由于新出现的a比任何的都小,同样也是先手必败,因为先手一上来就动不了.之后再枚举下去,可以发现这个题第一点应该是线性递推的,第二点肯定跟字典序的相关大小有关.容易想到:如果当前的这一位新加的字符是最小的,先手就一定必败.因此这个题也就做出来了:只要手上是当前序列最小的,那么就是先手必败,否则可以直接掏空整个序列使对手必败.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	string s;cin >> s;
	int n;n = s.size();
	char minc = 'z';
	for(int i = 0;i < n;++i)
	{
		minc = min(minc,s[i]);
		if(minc == s[i])	cout << "Mike\n";
		else cout << "Ann\n";
	}
    return 0;
}

D. Alex and Julian

原题大意:给定一个$n$个数没有重复的集合B.认为所有的整数都是一个点,并且点的数量是无限的,对于任意的两个点$i,j$来说,如果$|i-j| \in B$则将两者之间连一条无向边.问集合B里最少删除掉多少个元素才能使整个图是一个二分图.要求输出删除的数量以及删除的具体元素有哪些.

数据范围:
$1 \leq n \leq 2 * 10^5$
$1 \leq b_i \leq 10^{18}$

思路

这题看起来就牛逼的很.先从简单情况入手:假如集合B里只有两个元素$x,y$.想让他们两个构成一个奇环,需要什么样的条件.可以发现对于每个点开始来说,如果真的构成了一个环,这个环上的边的个数跟起点是谁没什么关系,不妨就假设是从$1$开始的.那么如果构成了一个环,首先是存在两个最小的正整数$a,b$使这样一个方程成立:$1+ax=1+by$其实也就是从$1$出发走到了两个相同的点,这样就构成了一个环.那么这个环的长度就应该是$a+b$,由于未知数比较多,考虑消元.对于$ax=by$这个式子来说,他的意思实际上就是最小公倍数,就是一个最小的正整数满足$ax=by=lcm(x,y)$,所以长度之和就是$\frac{lcm(x,y)}{x}+\frac{lcm(x,y)}{y}$,进一步变成$\frac{x+y}{gcd(x,y)}$.由于这是一个分数,所以先可以把所有的$2$的因子除掉,那么怎样她才能是一个偶数的结果呢,显然下面一定是一个奇数了,因为$gcd(x,y)$里的偶因子不会多于上面的两者的偶因子的数量,所以关键在于上面的奇偶性,换句话说现在得到的$x'+y'$的奇偶性和原来的和的奇偶性是相同的,显然如果这两者之间有一个是奇数,那么就不能得到偶数,也就是说两者包含的$2$的因子的部分应该是相同的.比如#$3$和$5$的是相同的,两者都没有,$4和4$是相同的,他们都有一个$4$.但是$4$和$8$是不同的,因为一个是$4$一个是$8$.如果两个不同,则在去掉最多的公共的$2$的因子之后,会出现一个奇数一个偶数,结果必然也还是一个奇数,就不符合了.经过这么一通分析,可以发现如果两个元素组成的环不是一个奇环,那么就要求这两个元素最后一位$1$的位置是相同的才行.因此到这里就可以想到整个题的做法了,就是找出所有元素的最后一位的$1$的位置再进行分组,在其中找出一组数量最多的就是答案所需要的一组,其他的全部删掉.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
int a[N];
int main()
{
	int n;scanf("%d",&n);
	vector<ll> group[70];
	for(int i = 1;i <= n;++i)
	{
		ll x;scanf("%lld",&x);
		ll p = x;
		int fnl = 0;
		while(x)
		{
			if(x & 1)	
			{
				group[fnl].push_back(p);
				break;
			}
			++fnl;
			x >>= 1;
		}
	}
	// for(int i = 0;i < 70;++i)
	// {
		// if(!group[i].empty())
		// {
			// cout << i << endl;
			// for(auto& v : group[i])
				// cout << v << " " ;
			// cout << endl;
		// }
	// }	
	int res = 0,pos = -1;
	for(int i = 0;i < 70;++i)
	{
		if(res < group[i].size())
		{
			res = group[i].size();
			pos = i;
		}
	}
	printf("%d\n",n - res);
	if(pos != -1)
	{
		// cout << "*" << pos << endl;
		for(int i = 0;i < 70;++i)
			if(i != pos && !group[i].empty())
			{
				for(auto& v : group[i])
					printf("%lld ",v);
			}
	}
    return 0;
}